// 680. 验证回文字符串Ⅱ： https://leetcode-cn.com/problems/valid-palindrome-ii/
package greedy

// 贪心， 从两边进行判断，遇到不匹配就删，然后比较后序是否是回文
// 判断是否是回文串，利用双指针
func validPalindrome(s string) bool {
	left, right := 0, len(s)-1
	for left < right {
		// 相等就继续进行
		if s[left] == s[right] {
			left++
			right--
			// 当不相等的时候，就要删除左右随机一个，再进行判断了
		} else {
			// 跳过这个单词，模拟删除的过程
			// 定义一个函数来判断，剩下的是否为回文串， 没有删除的机会了！！， 如果不是回文串就返回 false， 否则返回true
			return isPalindrome(s, left+1, right) || isPalindrome(s, left, right-1)
		}
	}
	// 遍历结束了，证明不用删除，就是个回文串
	return true
}

func isPalindrome(s string, left, right int) bool {
	for left < right {
		if s[left] == s[right] {
			left++
			right--
		} else {
			return false
		}
	}
	return true
}
